package com.kongge.algorithm.demo;

import com.kongge.algorithm.tree.TreeNode;

/**
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表，要求不能创建任何新的结点，只能调整树中结点指针的指向。
 * @author gaoshiqi
 *
 */
public class ConvertBinaryTreeToTwoWayLinkList implements IAlgorithm {

	public void execute() {
		TreeNode<Integer> root = TreeNode.createTree(new Integer[] {10, 6, 14, 4, 8, 12, 16});
		converTree(root);
		
		while (root != null && root.left != null) {
			root = root.left;
		}
		TreeNode<Integer> tempNode = root;
		while (tempNode != null) {
			System.out.print(tempNode.value + " ");
			tempNode = tempNode.right;
		}
	}
	
	private void converTree(TreeNode<Integer> root) {
		if (root == null) {
			return;
		}
		TreeNode<Integer> leftMaxNode = null;
		TreeNode<Integer> rightMinNode = null;
		if (root.left != null) {
			leftMaxNode = getLeftMaxNode(root.left);
			converTree(root.left);
		}
		
		if (root.right != null) {
			rightMinNode = getRightMinNode(root.right);
			converTree(root.right);
		}
		if (leftMaxNode != null) {
			leftMaxNode.right = root;
		}
		if (rightMinNode != null) {
			rightMinNode.left = root;
		}
	}
	
	private TreeNode<Integer> getLeftMaxNode(TreeNode<Integer> root) {
		if (root == null) {
			return null;
		}
		TreeNode<Integer> tempNode = root;
		while (tempNode.right != null) {
			tempNode = tempNode.right;
		}
		return tempNode;
	}
	
	private TreeNode<Integer> getRightMinNode(TreeNode<Integer> root) {
		if (root == null) {
			return null;
		}
		TreeNode<Integer> tempNode = root;
		while (tempNode.left != null) {
			tempNode = tempNode.left;
		}
		return tempNode;
	}

}
